#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


// 插入排序：当一列已经有序，再有加入的数据时，适合使用插入排序，它是一种简单直观且稳定的算法（不需要交换）
void insert_sort(int* arr,size_t len)
{
	for(int i=1; i<len; i++)
	{
		int t = arr[i] , k = i;					
		for(int j=i-1; j>=0 && arr[j] > t; j--)		//取 t=arr[i] 与在arr[i]前面的数进行比较
		{
			arr[j+1] = arr[j];						//当前面的数大于t时，将此数往后挪
			k = j;									//记录下标
		}											//当前面没有大于t的数时跳出循环
		arr[k] = t;									//将t插入此时的位置
	}
}

void show_arr(int* arr,size_t len)	//显示函数
{
	for(int i=0; i<len; i++)
	{
		printf("%d ",arr[i]);
	}
	printf("\n");
}

int main()
{
	int arr[10];

	for(int i=0; i<10; i++)
	{
		arr[i] = rand() % 100;
	}
	show_arr(arr,10);			//显示初始数组
	insert_sort(arr,1000);		//进行插入排序
	show_arr(arr,10);			//显示排序后的数组

}